package nf.utility;

import java.util.Map;
import java.util.HashMap;
import java.util.ArrayList;
import java.util.List;
import nf.util.Rational;
import nf.graph.Node;
import nf.graph.Graph;
import nf.graph.Path;

/**
 * A utility calculator that gives value to the heads and tails of all shortest
 * paths.
 */
public class InfantileUtilityCalculator extends UtilityCalculator
{
	public Map<Node, Rational> getUtilities(Graph graph)
	{
		int size = graph.size();
		List<Node> canonicalOrder = new ArrayList<Node>(graph);
		Map<Node, Rational> utilities =
			new HashMap<Node, Rational>(size / 2 * 3);
		
		for (int i = 0; i < size; i++) {
			Node node = canonicalOrder.get(i);
			List<Node> neighbors = graph.getNeighbors(node);
			Rational utility = new Rational();
			
			for (Node neighbor : neighbors) {
				utility = utility.subtract(getEdgeCost(node, neighbor));
			}
			
			utilities.put(node, utility);
		}
		
		for (int i = 0; i < size; i++) {
			Node head = canonicalOrder.get(i);
			Map<Node, Path> shortestPaths = graph.findShortestPaths(head);
			
			for (int j = (i + 1); j < size; j++) {
				Node tail = canonicalOrder.get(j);
				Path path = shortestPaths.get(canonicalOrder.get(j));
				if (path == null)
					continue;
				
				Rational value = new Rational(1, path.getLength());
				
				for (Node n : new Node[] { head, tail }) {
					traceValue(n, value, head, tail);
					Rational utility = utilities.get(n);
					utilities.put(n, utility.add(value));
				}
			}
		}
		
		return utilities;
	}
}
